问题：

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I’ll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!

Example:
n = 10, I pick 6.
Return 6.

思路

注意，这里有几个陷阱，一是你要理解my的含义，它的my是指的出题人，而我们是解题人，所以如果返回-1，说明它的数小，我们猜的数大，这里一定要理解！

这是一个经典的二分题目，很容易套用二分查找的公式写出来：

  1. public class Solution extends GuessGame {
  2.     public int guessNumber(int n) {
  3.         int st = 1, ed = n;
  4.         while(st < ed)
  5.         {
  6.             int mid = (st + ed) / 2;
  7.             if(guess(mid) == 0)
  8.                 return mid;
  9.             else if(guess(mid) < 0)  // the number is too large
  10.                 ed = mid-1;
  11.             else
  12.                 st = mid+1;
  13.         }
  14.         return st;
  15.     }
  16. }

看上去没问题，但是实际上有潜在的危险，比如这个例子就A不过去：

your text

为什么，因为int mid = (st + ed) / 2;可能会由于（st+ed）产生溢出！！

所以，为了解决这个问题，推荐把mid的写法写成下面的格式：

  1. int mid = st + (ed - st) / 2;

然后再A就能通过